package string.leetcode;

/**
 * 至少有k个连续字符的最长子串
 * @Author: yuisama
 * @Date: 2022/4/11 16:38
 * @Description:
 */
public class Num395_LongestSubString {
    // 1.分治法，将s中所有出现次数小于k的字符找出来拆分字符串(因为出现频率小于k的字符一定不在答案子串中，所以将s按照其进行拆分)
    // ，就能找到最长子串
    // 传入一个字符串s和要求的每个字符出现的最少次数k，就能求出最长子串长度
    public int longestSubstring(String s, int k) {
        // 终止条件，s.length() < k ,一定不存在解
        if (s.length() < k) {
            return 0;
        }
        // 统计出每个出现的字符以及其频率
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a'] ++;
        }
        // 遍历s中每个字符，找出出现频次 < k的字符，将字符串拆分
        // 为何要找到小于k的字符呢，因为出现频次大于k的字符一定是满足题意的子串
        // 因此我们按照小于k的字符将字符串拆分，找到最大值
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 这里只需要碰到第一个小于k的字符就可以返回答案了，因为结果一定不包含当前字符，
            // 最长子串一定在递归的结果中
            if (freq[c - 'a'] < k) {
                // 将字符串s按照c拆分，找最大子串
                int ret = 0;
                for (String str : s.split(String.valueOf(c))) {
                    ret = Math.max(ret,longestSubstring(str,k));
                }
                // 走完for循环的ret一定是最长子串
                return ret;
            }
        }
        // s中所有出现的字符频次都 >=k，则s本身就是最长子串
        return s.length();
    }
}
